#include<iostream>
#include<string>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;

//每次选两个权最小结点作为左右节点，和作为根节点，然后根节点入堆，不断重复

struct node
{
	node(char ch, int count)
		:_ch(ch)
		, _count(count)
		, _left(nullptr)
		,_right(nullptr)
	{}

	char _ch;
	int _count;
	node* _left;
	node* _right;

};


void dfs(node* root, string s, vector<pair<char, string>>& v)
{
	if (root == nullptr)
	{
		return;
	}
	dfs(root->_left, s + '0', v);
	dfs(root->_right, s + '1', v);
	if (root->_left == nullptr && root->_right == nullptr)
	{
		v.push_back({ root->_ch,s });
	}
}

struct func
{
	bool operator()(node* a, node* b) const//库中的堆会创一个const的func对象，然后调用方法，this默认是func *const this，所以必须加上const成const func * const this
	{
		return a->_count > b->_count;

	}

};
int main()
{
	string s;

	do {
		vector<pair<char, string>> v;
		cin >> s;
		if (s == "0") break;

		unordered_map<char, int> hash;
		for (auto e : s)
		{
			hash[e]++;
		}
		for (char ch = 'a';ch <= 'z';ch++)
		{
			if (hash.find(ch) != hash.end())
			{
				cout << ch << ":" << hash[ch] << " ";
			}
		}
		cout << endl;
		priority_queue<node*, vector<node*>, func> heap;//lamda表达式是一个函数对象，不是一个类型
		for (auto& e : hash)
		{
			node* p = new node(e.first, e.second);
			heap.push(p);
		}
		while (heap.size() > 1)
		{
			node* p1 = heap.top();heap.pop();
			node* p2 = heap.top();heap.pop();
			node* p = new node(0, p1->_count + p2->_count);
			p->_left = p1;
			p->_right = p2;

			heap.push(p);
		}
		dfs(heap.top(), "", v);
		sort(v.begin(), v.end());
		for (auto& e : v)
		{
			cout << e.first << ":" << e.second << " ";
		}
		cout<<endl;
		unordered_map<char,string> h(v.begin(),v.end());
		string t;
		for(auto e:s)
		{
			t+=h[e];
		}
		cout<<t<<endl;
		
		
		
		
		
		unordered_map<string,char> ha;
		for(auto e:v)
		{
			ha.insert({e.second,e.first});
		}
		string tmp,ret;
	
		for(int i=0;i<t.size();i++)
		{
			tmp+=t[i];
			if(ha.find(tmp)!=ha.end())
			{
				ret+=ha[tmp];	
				tmp="";			
			}
			
			
		}
		cout<<ret<<endl;
		cout << endl;
		cout << endl;
	} while (true);





	return 0;
}